#include <bits/stdc++.h>
#pragma	GCC	optimize(3)

using namespace std;

struct node
{
	int	val,size,cnt,key; node	*l,*r; node() {}
	node(const int x) {val=x,size=cnt=1,key=rand(); l=r=0;}
};

template<class _tp,const int MAX_SIZE>
struct ALLOC_
{
	_tp	*U; stack<_tp*>Trash; int ALL; ALLOC_(){U=new _tp[MAX_SIZE],ALL=0;}
	void	recycle(_tp* t) { Trash.push(t); return ; }
	_tp*	alloc()
	{
		if(!Trash.empty()) { _tp *t=Trash.top();Trash.pop(); return t; }
		return U+(++ALL);
	}
};

ALLOC_<node,1100000>	U;

struct Treap
{
	node	*root; Treap() { root=0; }

	void	update(node * t)
	{
		t->size=(t->l?t->l->size:0)+
			(t->r?t->r->size:0)+t->cnt;
	}

	void	lturn(node *&t)
	{ node * temp=t; t=t->r; temp->r=t->l;
		t->l=temp; update(t->l); update(t); }
	void	rturn(node *&t)
	{ node * temp=t; t=t->l; temp->l=t->r;
		t->r=temp; update(t->r); update(t); }

	void	insert(node *&t,const int d)
	{
		if(!t)return t=U.alloc(),*t=node(d),(void)0;
		t->size++; if(t->val==d)t->cnt++;
		else if(d>t->val) { insert(t->r,d); if(t->r->key<t->key)lturn(t); }
		else 
		{ insert(t->l,d);
		 if(t->l->key<t->key)rturn(t); }
		return ;
	}

	void	erase(node *&t,const int d)
	{
		if(!t)return ; if(t->val==d)
		{
			if(t->cnt>1)return t->cnt--,t->size--,(void)0;
			if(!t->l || !t->r)
			{
				node *temp=t;
				t=(t->l?t->l:(t->r?t->r:0));
				U.recycle(temp);
			}
			else if(t->l->key<t->r->key)rturn(t),erase(t,d);
			else	lturn(t),erase(t,d);
		}
		else if(d>t->val)t->size--,erase(t->r,d);
		else	t->size--,erase(t->l,d); return ;
	}

	int	get_kth(node *t,const int pos)
	{
		if(!t)return 0;
		if(t->l && pos<=t->l->size)return get_kth(t->l,pos);
		if(t->cnt+(t->l?t->l->size:0)==pos)return t->val;
		return get_kth(t->r,pos-(t->cnt+(t->l?t->l->size:0)));
	}

	int	get_rank(node *t,const int pos,const int step)
	{
		if(!t)return step;
		if(pos==t->val)return step+(t->l?t->l->size:0);
		else if(pos<t->val)return get_rank(t->l,pos,step);
		return get_rank(t->r,pos,step+(t->l?t->l->size:0)+t->cnt);
	}

	int	get_rank_(node *t,const int pos,const int step)
	{
		if(!t)return step;
		if(pos==t->val)return step+(t->l?t->l->size:0)+t->cnt;
		else if(pos<t->val)return get_rank_(t->l,pos,step);
		return get_rank_(t->r,pos,step+(t->l?t->l->size:0)+t->cnt);
	}

	void	insert(const int x) { insert(root,x); }
	void	erase(const int x) { erase(root,x); }
	int	get_kth(const int k) { return get_kth(root,k); }
	int	get_rank(const int x) { return get_rank(root,x,0); }
	int	get_rank_(const int x) { return get_rank_(root,x,0); }
}S[150000];

int	n,m,a[51000];

void	Build(const int l,const int r,const int num)
{
	if(l==r) { S[num].insert(a[l]); return ; }
	int	mid=l+((r-l)>>1);
	Build(l,mid,num<<1); Build(mid+1,r,num<<1|1);
	for(int i=l;i<=r;++i)S[num].insert(a[i]); return ;
}

int	Query_rank(const int l,const int r,const int num,const int s,const int t,const int d)
{
	if(s<=l && r<=t) return S[num].get_rank(d);
	int	mid=l+((r-l)>>1);
	if(t<=mid)return Query_rank(l,mid,num<<1,s,t,d);
	if(s>mid)return Query_rank(mid+1,r,num<<1|1,s,t,d);
	return Query_rank(l,mid,num<<1,s,t,d)+Query_rank(mid+1,r,num<<1|1,s,t,d);
}

int	Query_rank_(const int l,const int r,const int num,const int s,const int t,const int d)
{
	if(s<=l && r<=t) return S[num].get_rank_(d);
	int	mid=l+((r-l)>>1);
	if(t<=mid)return Query_rank_(l,mid,num<<1,s,t,d);
	if(s>mid)return Query_rank_(mid+1,r,num<<1|1,s,t,d);
	return Query_rank_(l,mid,num<<1,s,t,d)+Query_rank_(mid+1,r,num<<1|1,s,t,d);
}

void	Query_kth_range(const int l,const int r,const int num,
		const int s,const int t,const int d, vector<int>&vec)
{
	if(s<=l && r<=t)return vec.push_back(num),(void)0;
	int	mid=l+((r-l)>>1);
	if(s<=mid)Query_kth_range(l,mid,num<<1,s,t,d,vec);
	if(t>mid)Query_kth_range(mid+1,r,num<<1|1,s,t,d,vec);
	return ;
}

int	_get_rank(const int d,vector<int>&vec)
{
	int	temp=0;
	for(int i=0;i<(int)vec.size();++i)
		temp+=S[vec[i]].get_rank(d);
	return temp;
}

int	Query_kth(const int s,const int t,const int d)
{
	vector<int>vec;Query_kth_range(1,n,1,s,t,d,vec);
	int	l=-1,r=1e8+1;
	while(l<r-1)
	{
		int mid=l+((r-l)>>1);
		if(_get_rank(mid,vec)<d)l=mid;
		else	r=mid;
	}
	return l;
}

void	Change(const int l,const int r,const int num,const int s,const int d,const int dd)
{
	if(l==r) { S[num].erase(d); S[num].insert(dd); return ; }
	int	mid=l+((r-l)>>1);
	if(s<=mid)Change(l,mid,num<<1,s,d,dd);
	else	Change(mid+1,r,num<<1|1,s,d,dd);
	S[num].erase(d);S[num].insert(dd); return ;
}

#warning	Complexity log BIG CONSTANT
int	Query_pre(const int s,const int t,const int d)
{ return Query_kth(s,t,Query_rank(1,n,1,s,t,d)); }
int	Query_nxt(const int s,const int t,const int d)
{ return Query_kth(s,t,Query_rank_(1,n,1,s,t,d)+1); }

int main()
{
	int	i,op,l,r,k,x;

	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
		scanf("%d",&a[i]);
	Build(1,n,1);
	while(m--)
	{
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",Query_rank(1,n,1,l,r,k)+1);
		}
		else if(op==2)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",Query_kth(l,r,k));
		}
		else if(op==3)
		{
			scanf("%d%d",&x,&k);
			Change(1,n,1,x,a[x],k);a[x]=k;
		}
		else if(op==4)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",Query_pre(l,r,k));
		}
		else if(op==5)
		{
			scanf("%d%d%d",&l,&r,&k);
			printf("%d\n",Query_nxt(l,r,k));
		}
	}
	return 0;
}

